package com.fulin.leetcode;

import java.util.Arrays;

/**
 * TODO
 *
 * @Author fulin
 * @Date 2023/1/31 17:55
 **/
public class Num1578_使绳子变为彩色的最短时间 {

    /**
     * 动态规划算法
     *
     * @param colors
     * @param neededTime
     * @return
     */
    public int minCost(String colors, int[] neededTime) {
        int len = neededTime.length;
        int[] dp = new int[len];
        dp[0] = 0;
        int lastMin = 0;
        for(int i = 1; i < colors.length();i++){
            if(colors.charAt(i) != colors.charAt(i-1)){
                dp[i] = dp[i-1];
                lastMin = i;
            }else{
                if(neededTime[lastMin] < neededTime[i]){
                    dp[i] = dp[i-1] + neededTime[lastMin];
                    lastMin = i;
                }else{
                    dp[i] = dp[i-1] + neededTime[i];
                }
            }
        }
        return dp[len -1];
    }

    /**
     * 遍历算法
     * @param colors
     * @param neededTime
     * @return
     */
    public int minCost2(String colors, int[] neededTime) {
        int len = neededTime.length;
        int total = 0;
        for(int i = 1; i < colors.length();i++){
            if(colors.charAt(i-1) != colors.charAt(i)){
                continue;
            }
            int stepTime = colors.charAt(i-1);
            int max = neededTime[i-1];
            while(colors.charAt(i-1) == colors.charAt(i)){
                stepTime += neededTime[i];
                if(neededTime[i] > max){
                    max = neededTime[i];
                }
                if(i == len -1){
                    break;
                }
                i++;
            }
            total += stepTime - max;
        }
        return total;
    }

}
